package huadi.algorithm.sort;

import static huadi.algorithm.sort.SortingUtil.swap;

/**
 * HeapSort 堆排序
 *
 * @author Huadi
 * @version 2011-11-9
 */
public class HeapSort {
    public static void sort(int[] array) {
        initMaxHeap(array);
        for (int i = array.length - 1; i > 0; i--) {
            swap(array, 0, i);
            buildMaxHeap(array, 0, i - 1);
        }
    }

    private static void initMaxHeap(int[] array) {
        for (int i = array.length >> 1; i > 0; i--) {
            buildMaxHeap(array, i, array.length - 1);
        }
    }

    /**
     * The method to build the MaxHeap using iteration instead of recursive.
     *
     * @param array      the array to sort
     * @param beginIndex the heap root in the array's index
     * @param endIndex   the heap size in the array's index
     */
    private static void buildMaxHeap(int[] array, final int beginIndex, final int endIndex) {
        if (beginIndex >= endIndex || beginIndex << 1 >= endIndex) return;
        if (array[beginIndex] >= array[beginIndex << 1] && array[beginIndex] >= array[(beginIndex << 1) + 1]) return;

        int node = beginIndex;
        do {
            if (array[node << 1] > array[(node << 1) + 1]) {
                swap(array, node, node << 1);
                node = node << 1;
            } else {
                swap(array, node, (node << 1) + 1);
                node = (node << 1) + 1;
            }
        } while ((node << 1) < endIndex);
    }

    /**
     * Method to build the MaxHeap using recursive.
     *
     * @param array      the array to sort
     * @param beginIndex heap root node index
     * @param endIndex   the heap size in the array's index
     */
    private static void buildMaxHeapRecursive(int[] array, final int beginIndex, final int endIndex) {
        // 判断递归出口.
        // (beginIndex * 2 >= endIndex) 说明当前堆顶是叶子节点.
        if (beginIndex >= endIndex || beginIndex << 1 >= endIndex) return;
        // 如果当前堆顶比它之下的两个节点都大, 说明该大顶堆成立.
        if (array[beginIndex] >= array[beginIndex << 1] && array[beginIndex] >= array[(beginIndex << 1) + 1]) return;

        // 大顶堆被破坏，需要重新建立大顶堆。
        // 判断下方2个节点哪个比较大, 与其交换并递归build下方的二叉树.
        if (array[beginIndex << 1] > array[(beginIndex << 1) + 1]) {// 左子树大于右子树，与左子树交换
            swap(array, beginIndex, beginIndex << 1);
            buildMaxHeapRecursive(array, beginIndex << 1, endIndex);
        } else {// 左子树小于右子树，与右子树交换
            swap(array, beginIndex, (beginIndex << 1) + 1);
            buildMaxHeapRecursive(array, (beginIndex << 1) + 1, endIndex);
        }
    }

}
